//
// Created by Administrator on 2021/11/22.
//
# include<iostream>
# include<vector>
using namespace std;

void printVector(vector<int> vec){
    for (int i : vec){
        cout<<i<<" ";
    }
    cout<<endl;
}

void permuteHelper(vector<int> &nums, vector<int> &chosen, vector<vector <int>> &result){
    //base case
    if(nums.empty()){
        printVector(chosen);
        result.push_back(chosen);
    }else{
        for(auto i=nums.begin();i<nums.end();i++) {
            //choose
            int choose_i = *i;
            chosen.push_back(choose_i);
            nums.erase(i);
            //explore
            cout<<"I choose "<<choose_i<<endl;
            printVector(nums);
            printVector(chosen);
            permuteHelper(nums,chosen,result);
            //un-choose
            chosen.pop_back();
            nums.insert(i,choose_i);
            cout<<"I un-choose "<<choose_i<<endl;
            printVector(nums);
            printVector(chosen);
        }
    }
}

vector<vector <int>> permute(vector<int> &nums){
    vector<int> chosen;
    vector<vector <int>> result;
    permuteHelper(nums,chosen,result);
    return result;
}




//int main() {
//    vector<int> nums = {1,2,3};
//    vector<vector <int>> result;
//    result = permute(nums);
//    for (vector<int> i:result){
//        printVector(i);
//    }
//    return 0;
//}
